Alien Invasion

Memory limit: 128 MB

In the Byteland Department of Exobiology the Institute of Space Hazard has been established. All its employed researchers are to protect the citizens of Byteland from the disastrous effects of an alien invasion, which unfortunately undoubtedly is going to happen.

There are cities in Byteland situated along the Byteroad. Cities are numbered through and the -th city has inhabitants.

It is a common knowledge that aliens always invade during the night and they can only invade a single city at once. Unfortunately all the inhabitants of an invaded city are instantaneously kidnapped and transported to a different galaxy.

Researchers of the institute try to find a way of securing the citizens. As aliens are not interested in rodents (such as rats), researchers decided to exploit this fact and use rats as a warning system. When aliens invade a city, two rats leave this city in opposite directions of the Byteroad, spreading the news of invasion. A rat needs almost one day to go between two neighboring cities, hence the news sent from an -th city reaches a -th city just before the dusk of the -th day after the invasion. After hearing the news alarmed citizens hide themselves in shelters, staying out of reach of alien's tentacles. As Byteland's shelters are well-equipped, warned citizens stay in the shelters until the aliens stop invading Byteland and go back to their galaxy.

As you can see the described warning system may not save all the citizens. Researchers try to figure out the worst case scenario, that is, the maximum number of citizens that may be kidnapped.

Input

The first line of input contains a single integer (), the number of cities in Byteland. The second line of input contains a sequence of integers (), describing the number of inhabitants of subsequent cities along the Byteroad.

Output

The first and only line of output should contain a single integer: the number of kidnapped citizens in the worst case scenario.

Example

For the input data:

6
5 9 1 3 7 2

the correct result is:

16

Task author: Tomasz Idziaszek.